# 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 
# 
#  示例 1 : 
# 
#  
# 输入:nums = [1,1,1], k = 2
# 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
#  
# 
#  说明 : 
# 
#  
#  数组的长度为 [1, 20,000]。 
#  数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。 
#  
#  Related Topics 数组 哈希表 
#  👍 583 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 无法通过nums数字特别多的测试用例，需要优化
        # if len(nums) == 0:
        #     if k == 0:
        #         return 1
        #     else:
        #         return 0
        # n = len(nums)
        # record = [0 for _ in range(0, n)]
        # record[0] = nums[0]
        # for i in range(1, n):
        #     record[i] = record[i - 1] + nums[i]
        #
        # count = 0
        # for i in range(0, n):
        #     for j in range(i, n):
        #         if nums[i] + record[j] - record[i] == k:
        #             count += 1
        # return count

        map = {}
        n = len(nums)
        sum = 0
        # 默认不加任何元素，部分和为零的情况有一种
        # 即 刚好前面的数字相加等于 k
        map[0] = 1
        count = 0
        for i in range(0, n):
            sum += nums[i]

            if map.get(sum - k):
                count += map.get(sum - k)

            map[sum] = map.get(sum, 0) + 1

        return count
            # leetcode submit region end(Prohibit modification and deletion)


print(Solution().subarraySum([1, 1, 1], 2))
